Finding one's way to a given location (for example to Helsinki City Hall) is a necessity that everyone encounters sometimes. Merely pointing the direction of the destination is not usually enough. Information is needed on how the destination can be reached from the current location by the available traffic routes.
To solve this problem, for example orientation computers to be installed in a car, which position the car by means of Global Positioning System (GPS) signals and in which the driving instructions are shown on a screen on a map or are given via a loudspeaker as spoken instructions, are available. In these systems, the driving instructions are based on map information stored on a CD-ROM or another form of mass storage. This map information includes a description of the road system in such a way that the route between two points can be retrieved from software. The map also has information on the course of the roads on the basis of which the position indicated by the GPS or other method of positioning can be placed in this road system.
During 1999, the first map service intended for WAP (Wireless Application Protocol) workstations was introduced in Finland. When the map information is on a common server in the network, individual users need not attend to the updating of their map database.
Three-dimensional virtual models have come alongside conventional maps as means of representing areas. Such 3D models are much more illustrative than maps, since in many instances they can serve in orientation and finding the destination better than conventional maps.
Virtual models and maps are not mutually exclusive alternatives, however. The best way to represent a route may be to show its course on a map and simultaneously to show the views along the route in another window, using the 3D model.
Mobile stations are evolving into mobile workstations communicating with data networks. GPS-based solutions, and more recently also solutions utilizing the actual mobile communications network, such as the GSM base station network, have been developed for positioning them.
The latest mobile workstation models in the year 2000 already have displays capable of graphical representation. For example the palm-sized Palm III computer published in February 2000 already has a colour display, whose resolution is sufficient for representing identifiable images of virtual city landscapes.
However, there are still basically two bottlenecks in the mobile use of three-dimensional models: the transmission capacity of the telecommunications network and the storage capacity of the terminal. By the present standards, the quantity of data relating to three-dimensional models is enormous. Transmission of model entities larger than a few blocks at the present data transfer rates of the GSM network, for example, is not practical. Even though the UMTS technology is expected to increase the transfer rate in the actual mobile network many tenfolds, the bottlenecks in the backbone of the Internet will restrict the available transmission capacity. Already with the present fixed ISDN-grade connections the bottleneck is usually constituted by the Internet and not the actual ISDN connection.
The starting point in the prior art is usually the notion that it cannot be known in advance from which direction the 3D objects included in the virtual model are viewed. If for example a virtual city comprises a house around which the user (or more specifically, the camera point representing his eyes) can move freely, the model must include all walls, roof panes and other such parts of the house.
Research and development in the field has centered on the problems of the freely mobile user. There is much prior art by means of which it is attempted to optimize the presentation of a 3D model employed through a data network and the data communication in the network. This work is divided into two main streams:
1. The ‘progressive mesh’ techniques strive to optimize the down-loading of individual objects through the network in such a way that a coarse model is downloaded first and thereafter more details are retrieved thereinto. Cf. e.g. http://research.microsoft.com/users/hhoppe/.
2. Many solutions seek an optimization of what parts of the model are retrieved through the network on the basis of the distance or visibility of the parts of the model. The aim is to avoid retrieval of information on objects that are not visible on account of the distance, visual obstructions, or for other reasons. U.S. Pat. No. 5,675,721 is an example of the prior art of this trend of development.
However, the drawback of the known technology described above is mainly the fact that the possibilities for optimizing the amount of data to be transmitted to the user through the telecommunications network are restricted. The models must always contain a lot of information, since it is not known in advance which parts of the model can come into the user's view and in what order the nearby parts of the model will come visible to the user.
It is an object of the present invention to eliminate this drawback and to provide a solution to the problem of how the 3D model can be used in route guidance when the amount of data to be transmitted is to be minimized on account of the restrictions of the data transmission capacity available and the memory and processing capacity of the workstation.